//跳表实现得排行榜
#pragma once

#include <unordered_map>
#include <cmath>
#include <list>
#include <functional>
#include "typedef.h"
#include "log_def.h" //不同项目，需要改。 日志宏  #include "base/core/log.h"


template <typename Key, typename Value>
struct skiplistNode
{
	//每层的节点信息
	struct zskiplistLevel
	{
		skiplistNode<Key, Value>* forward = nullptr;  //当前层当前节点下一个节点
		unsigned long span = 0; //该层中当前节点与下一结点之间相隔几个节点(在level[0]中的结点数,level[0]节点是连续的该值为0)
	};

	Value value;//分数对应的对象信息,必须是一个可以比较的类型，必须实现对象的比较操作符
	Key key;		//排序key，必须是一个可以比较的类型，必须实现对象的比较操作符(一般位数值类型(long,int,double等))
	skiplistNode* backward = nullptr; //第0层的回溯指针
	int level = 0;
	zskiplistLevel* levels = nullptr;

	skiplistNode(int level)
	{
		if (level <= 0)
		{
			LERROR("error");
			return;
		}
		this->level = level;
		this->levels = new zskiplistLevel[level];
		for (int i = 0; i < level; i++)
		{
			this->levels[i].forward = nullptr;
			this->levels[i].span = 0;
		}
	}

	~skiplistNode()
	{
		if (levels) delete[] levels;
		levels = nullptr;
		backward = nullptr;
	}
};

template <typename Key, typename Value>
struct skiplist
{
	skiplistNode<Key, Value>* header = nullptr, * tail = nullptr; //header和tail分别指向头结点和尾结点，头节点到尾节点，从大到小排序
	unsigned long length = 0; //结点数量，
	int level = 0; //level为表中结点的最高等级。 1开始.  最底层连接 节点数最多
};


template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL = 64>/* Should be enough for 2^64 elements */
class RankSkipList
{

private:

	std::unordered_map<Key, skiplistNode<Key, Value>*> m_map;
	skiplist<Key, Value> m_skiplist;
	uint32 mrankMaxLen = 0;//排行榜最大长度 0 不限制

public:
	/**
	 * 注意初始化的时候跳表的头部指针已经存在但是长度为0
	 */
	RankSkipList(uint32 rankMaxLen=0);
	~RankSkipList();

	/**
	 * 插入一个新的节点如果key已存在，则更新积分
	 * @param value
	 * @param key
	 * @return 插入的skiplistNode
	 */
	const Value* Insert(Key key, Value value);
	/**
	 * 删除一个元素
	 * @param value
	 * @param key
	 * @return 1 ok 0 not found
	 */
	bool Remove(Key key);
	/**
	 *
	 * @param start
	 * @param end
	 * @param dict
	 */
	void RemoveByRank(unsigned long rank);
	/**
	 *
	 * @param start
	 * @param end
	 * @param dict
	 */
	void RemoveByRank(unsigned long start, unsigned long end);

	void Clear(); //删除所有排行榜数据

	/**
	 * 根据key获取排名和信息
	 * @param key
	 * @pValue 返回nullptr 表示不存在 
	 */
	using CPVALUE = const Value*;
	void Get(Key key, CPVALUE& pValue, unsigned long& rank) const;

	/**
	 * 获取排名
	 * @param key
	 * @return 0 不存在 [1,2^64] rank
	 */
	unsigned long Rank(Key key) const;

	/**
	 *获取指定排名的节点info
	 * @param rank
	 * @return
	 */
	const Value* GetByRank(unsigned long rank) const;

	/**
	 *获取指定范围排名的节点info
	 * @param rank
	 * @return rank[start,end]
	 */
	std::vector<const Value*> GetRangeByRank(unsigned long start, unsigned long end) const;

	//根据名次遍历
	void EachValue(std::function<void(uint32 rank, const Value&)> cb) const;

	//兼容for (const Value& v : skiplist)用。 
	struct Iter
	{
		friend class RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>;
	private:
		const skiplist<Key, Value>* m_skiplist = nullptr;
		const skiplistNode<Key, Value>* tmpNode = nullptr;

	public:
		Iter& operator++()
		{
			if (tmpNode == nullptr)
			{
				return *this;
			}
			tmpNode = tmpNode->levels[0].forward;
			return *this;
		}
		const Value& operator*()
		{
			if (tmpNode == nullptr)
			{
				static Value d;
				return d;
			}
			return tmpNode->value;
		}
		bool operator!=(const Iter& b)
		{
			return tmpNode != b.tmpNode;
		}
	};
	Iter begin() const
	{
		Iter it;
		if (m_skiplist.length == 0)
		{
			return it;
		}
		if (nullptr == m_skiplist.header)
		{
			return it;
		}
		it.m_skiplist = &m_skiplist;
		it.tmpNode = m_skiplist.header->levels[0].forward;
		return it;
	}
	Iter end() const
	{
		Iter it;
		return it;
	}

private:

	/**
	 * 创建一个节点
	 * @param level
	 * @param value
	 * @param value
	 * @return
	 */
	skiplistNode<Key, Value>* CreateSkipListNode(int level, Value value, Key key);
	/**
	 * 删除节点
	 * @param deleteNode
	 * @param update
	 */
	void DeleteNodeEx(skiplistNode<Key, Value>* deleteNode, skiplistNode<Key, Value>** update);

	//随机跳表的层数
	int RandomLevel(void)
	{
		const static uint ZSKIPLIST_P = 0.25 * 0xFFFF;      /* Skiplist P = 1/4 */
		int level = 1;
		while ((random() & 0xFFFF) < ZSKIPLIST_P)
			level += 1;
		return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
	}
};



template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL /*= 64*/>
RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::~RankSkipList()
{
	skiplistNode<Key, Value>* node = m_skiplist.header->levels[0].forward, * next = nullptr;
	delete m_skiplist.header;
	while (node) {
		next = node->levels[0].forward;
		delete node;
		node = next;
	}
}
template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL /*= 64*/>
RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::RankSkipList(uint32 rankMaxLen )
{
	m_skiplist.level = 1;
	m_skiplist.length = 0;
	m_skiplist.header = new skiplistNode<Key, Value>(ZSKIPLIST_MAXLEVEL);
	m_skiplist.tail = nullptr;
	mrankMaxLen = rankMaxLen;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
const Value* RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::Insert(Key key, Value value)
{
	skiplistNode<Key, Value>* update[ZSKIPLIST_MAXLEVEL]; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
	skiplistNode<Key, Value>* tmpNode = nullptr;

	auto it = m_map.find(key);
	//如果节点已存在，先删除老的节点
	if (it != m_map.end())
	{
		Value& curscore = it->second->value;
		tmpNode = m_skiplist.header;
		for (int i = m_skiplist.level - 1; i >= 0; i--) {
			//不可能出现这种情况，如果出现则说明跳表结构已经被破坏,排行榜已经乱了
			if (!(i < tmpNode->level))
			{
				LERROR("The data of skiplist is bad\n");
				return nullptr;
			}
			//如果当前节点的下一个节点is not nullptr，且他的下一个节点的value小于插入节点的value，或者他们积分相等但是key小于插入节点的key，则继续往后找，直到
			//找到条件不满足的跳出循环，则每层要update的节点的前一个节点都存在update数组中
			while (tmpNode->levels[i].forward &&
				( tmpNode->levels[i].forward->value > curscore ||
					(tmpNode->levels[i].forward->value == curscore && tmpNode->levels[i].forward->key > key)))
			{
				tmpNode = tmpNode->levels[i].forward;
			}
			update[i] = tmpNode;
		}

		tmpNode = tmpNode->levels[0].forward;
		//没找到???,不可能
		if (tmpNode == nullptr || tmpNode->key != it->second->key || !(tmpNode->value == it->second->value))
		{
			LERROR("Update value failed,update node not found \n");
			return nullptr;
		}
		//新的节点还在原有节点的中间，更新后的节点位置并不会发生变化，则直接更新积分
		if ((tmpNode->backward == nullptr || tmpNode->backward->value > value) &&
			(tmpNode->levels[0].forward == nullptr || value > tmpNode->levels[0].forward->value ))
		{
			tmpNode->value = value;
			return &tmpNode->value;
		}

		//删除老的节点
		DeleteNodeEx(tmpNode, update);
		m_map.erase(tmpNode->key);
		delete tmpNode;
	}

	unsigned int rank[ZSKIPLIST_MAXLEVEL];  //每一层要修改的结点的排名(根据value从小到大排序)
	//新增key,value
	tmpNode = m_skiplist.header;
	for (int i = m_skiplist.level - 1; i >= 0; i--)
	{
		//初始化 update数组和rank数组
		rank[i] = i == (m_skiplist.level - 1) ? 0 : rank[i + 1];
		//不可能出现这种情况，如果出现则说明跳表结构已经被破坏,排行榜已经乱了
		if (!(i < tmpNode->level))
		{
			LERROR("The data of skiplist is bad\n");
			return nullptr;
		}
		//如果当前节点的下一个节点is not nullptr，且他的下一个节点的value小于插入节点的value，或者他们积分相等但是key小于插入节点的key，则继续往后找，直到
		//找到条件不满足的跳出循环，则新插入的节点需要插入该层的当前节点后面，把此节点记录到update数组中
		while (tmpNode->levels[i].forward &&
			(tmpNode->levels[i].forward->value > value   ||
				(tmpNode->levels[i].forward->value == value && tmpNode->levels[i].forward->key > key)))
		{
			rank[i] += tmpNode->levels[i].span;  //该层中当前节点与下一结点之间在level[0]中的结点数累计的结果即每一层要修改的结点的排名
			tmpNode = tmpNode->levels[i].forward;
		}
		update[i] = tmpNode;
	}
	//如果长度==最大长度
	if (mrankMaxLen > 0 && m_skiplist.length == mrankMaxLen)
	{
		//如果更新的节点是最后一个(分最低),且新的分数比当前分数低直接返回，不进榜
		if (update[0]->levels[0].forward == NULL || tmpNode->levels[0].forward->value > value)
		{
			return NULL;
		}
	}
	//随机层数
	int level = RandomLevel();
	//如果随机的层数比当前skiplist的层数要大，则补充高出的层的每层update节点信息
	if (level > m_skiplist.level)
	{
		for (int i = m_skiplist.level; i < level; i++)
		{
			rank[i] = 0;
			update[i] = m_skiplist.header; //当前节点初始化为header
			update[i]->levels[i].span = m_skiplist.length; //span即skiplist的长度
		}
		m_skiplist.level = level;  //更新skiplist的层数
	}

	//创建节点
	tmpNode = CreateSkipListNode(level, value, key);
	for (int i = 0; i < level; i++)
	{
		//修改创建节点tmpNode,需要修改的节点的forward指针(从每层来看上是一个链表的插入操作即把tmpNode插入到update[i]后面)
		tmpNode->levels[i].forward = update[i]->levels[i].forward;
		update[i]->levels[i].forward = tmpNode;

		//修改相关节点的span
		tmpNode->levels[i].span = update[i]->levels[i].span - (rank[0] - rank[i]);
		update[i]->levels[i].span = (rank[0] - rank[i]) + 1;
	}

	//如果随机的层数小于当前skiplist的层数,因为插入了一个新的节点，则把每层需要修改的节点的span加1
	for (int i = level; i < m_skiplist.level; i++)
	{
		update[i]->levels[i].span++;
	}

	//在0层中把新插入节点的前向指针指向修改的指针
	tmpNode->backward = (update[0] == m_skiplist.header) ? nullptr : update[0];
	//如果新插入节点的后一个节点存在，则把他的前向指针指向新插入的节点
	if (tmpNode->levels[0].forward)
	{
		tmpNode->levels[0].forward->backward = tmpNode;
	}
	else {//否则新插入的节点为tail
		m_skiplist.tail = tmpNode;
	}
	m_skiplist.length++;
	//更新map
	m_map[key] = tmpNode;
	//如果长度大于最大长度
	if (mrankMaxLen > 0 && m_skiplist.length > mrankMaxLen)
	{
		RemoveByRank(mrankMaxLen + 1);
	}
	return &tmpNode->value;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
bool RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::Remove(Key key) {
	skiplistNode<Key, Value>* update[ZSKIPLIST_MAXLEVEL] = { 0 }; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
	skiplistNode<Key, Value>* tmpNode;
	int i;

	auto it = m_map.find(key);
	//如果节点已存在，先删除老的节点
	if (it != m_map.end())
	{
		Value& value = it->second->value;
		tmpNode = m_skiplist.header;
		for (i = m_skiplist.level - 1; i >= 0; i--) {
			//不可能出现这种情况，如果出现则说明跳表结构已经被破坏,排行榜已经乱了
			if (!(i < tmpNode->level))
			{
				printf("ERROR The data of skiplist is bad\n");
				return false;
			}
			//如果当前节点的下一个节点is not nullptr，且他的下一个节点的value小于插入节点的value，或者他们积分相等但是key小于插入节点的key，则继续往后找，直到
			//找到条件不满足的跳出循环，则每层要删除的节点的前一个节点都存在update数组中
			while (tmpNode->levels[i].forward &&
				( tmpNode->levels[i].forward->value > value ||
					(tmpNode->levels[i].forward->value == value && tmpNode->levels[i].forward->key > key)))
			{
				tmpNode = tmpNode->levels[i].forward;
			}
			update[i] = tmpNode;
		}

		tmpNode = tmpNode->levels[0].forward;
		//判断找到的节点是否是要删除的节点
		if (tmpNode && value == tmpNode->value && tmpNode->key == key) {
			DeleteNodeEx(tmpNode, update);
			m_map.erase(key);
			delete tmpNode;
			return true;
		}
	}

	return false; /* not found */
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::RemoveByRank(unsigned long rank)
{
	RemoveByRank(rank, rank);
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::RemoveByRank(unsigned long start, unsigned long end)
{
	skiplistNode<Key, Value>* update[ZSKIPLIST_MAXLEVEL]; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
	skiplistNode<Key, Value>* tmpNode;
	unsigned long traversed = 0, removed = 0;
	int i;

	tmpNode = m_skiplist.header;
	for (i = m_skiplist.level - 1; i >= 0; i--) {
		//不可能出现这种情况，如果出现则说明跳表结构已经被破坏,排行榜已经乱了
		if (!(i < tmpNode->level))
		{
			printf("ERROR The data of skiplist is bad\n");
			return;
		}
		while (tmpNode->levels[i].forward && (traversed + tmpNode->levels[i].span) < start) {
			traversed += tmpNode->levels[i].span;
			tmpNode = tmpNode->levels[i].forward;
		}
		update[i] = tmpNode;
	}

	traversed++;
	tmpNode = tmpNode->levels[0].forward;
	while (tmpNode && traversed <= end) {
		skiplistNode<Key, Value>* next = tmpNode->levels[0].forward;
		DeleteNodeEx(tmpNode, update);
		m_map.erase(tmpNode->key);
		delete  tmpNode;
		traversed++;
		tmpNode = next;
		removed++;
	}
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL /*= 64*/>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::Clear()
{
	skiplistNode<Key, Value>* update[ZSKIPLIST_MAXLEVEL]; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
	skiplistNode<Key, Value>* tmpNode;
	{
		unsigned long traversed = 0;
		int i;

		tmpNode = m_skiplist.header;
		for (i = m_skiplist.level - 1; i >= 0; i--) {
			//不可能出现这种情况，如果出现则说明跳表结构已经被破坏,排行榜已经乱了
			if (!(i < tmpNode->level))
			{
				printf("ERROR The data of skiplist is bad\n");
				return;
			}
			while (tmpNode->levels[i].forward && (traversed + tmpNode->levels[i].span) < 1) {
				traversed += tmpNode->levels[i].span;
				tmpNode = tmpNode->levels[i].forward;
			}
			update[i] = tmpNode;
		}
	}

	tmpNode = tmpNode->levels[0].forward;
	while (tmpNode ) {
		skiplistNode<Key, Value>* next = tmpNode->levels[0].forward;
		DeleteNodeEx(tmpNode, update);
		delete  tmpNode;
		tmpNode = next;
	}
	m_map.clear();
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL /*= 64*/>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::Get(Key key, RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::CPVALUE& pValue, unsigned long& outRank) const
{
	pValue = nullptr;
	outRank = 0;
	skiplistNode<Key, Value>* tmpNode;
	unsigned long rank = 0;
	int i;

	auto it = m_map.find(key);
	if (it == m_map.end())
	{
		return;
	}
	Value value = it->second->value;
	tmpNode = m_skiplist.header;
	for (i = m_skiplist.level - 1; i >= 0; i--) {
		//如果当前节点的下一个节点is not nullptr，且他的下一个节点的value小于插入节点的value，或者他们积分相等但是key小于等于插入节点的key，则继续往后找，直到
		//找到条件不满足的跳出循环
		while (tmpNode->levels[i].forward &&
			(tmpNode->levels[i].forward->value > value ||
				(tmpNode->levels[i].forward->value == value && tmpNode->levels[i].forward->key >= key))) {
			rank += tmpNode->levels[i].span;  //span该层中当前节点与下一结点之间在level[0]中的结点数累计的结果即每一层要修改的结点的排名
			tmpNode = tmpNode->levels[i].forward;
		}

		if (tmpNode->key && key == tmpNode->key) {
			outRank = rank;
			pValue = &tmpNode->value;
			return;
		}
	}
	return;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
unsigned long RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::Rank(Key key) const
{
	skiplistNode<Key, Value>* tmpNode;
	unsigned long rank = 0;
	int i;

	auto it = m_map.find(key);
	if (it == m_map.end())
	{
		return 0;
	}
	Value value = it->second->value;
	tmpNode = m_skiplist.header;
	for (i = m_skiplist.level - 1; i >= 0; i--) {
		//如果当前节点的下一个节点is not nullptr，且他的下一个节点的value小于插入节点的value，或者他们积分相等但是key小于等于插入节点的key，则继续往后找，直到
		//找到条件不满足的跳出循环
		while (tmpNode->levels[i].forward &&
			(tmpNode->levels[i].forward->value > value ||
				(tmpNode->levels[i].forward->value == value && tmpNode->levels[i].forward->key >= key))) {
			rank += tmpNode->levels[i].span;  //span该层中当前节点与下一结点之间在level[0]中的结点数累计的结果即每一层要修改的结点的排名
			tmpNode = tmpNode->levels[i].forward;
		}

		if (tmpNode->key && key == tmpNode->key) {
			return rank;
		}
	}
	return 0;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
const Value* RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::GetByRank(unsigned long rank) const
{
	skiplistNode<Key, Value>* tmpNode;
	unsigned long traversed = 0;
	int i;

	tmpNode = m_skiplist.header;
	for (i = m_skiplist.level - 1; i >= 0; i--) {
		while (tmpNode->levels[i].forward && (traversed + tmpNode->levels[i].span) <= rank)
		{
			traversed += tmpNode->levels[i].span;
			tmpNode = tmpNode->levels[i].forward;
		}
		if (traversed == rank) {
			return &tmpNode->value;
		}
	}
	return nullptr;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
std::vector<const Value*> RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::GetRangeByRank(unsigned long start, unsigned long end)const
{
	start = start <= 0 ? 1 : start;
	if (start > end)
	{
		return {};
	}
	const skiplistNode<Key, Value>* tmpNode = nullptr;
	do 
	{
		unsigned long rank = start;
		unsigned long traversed = 0;

		tmpNode = m_skiplist.header;
		for (int i = m_skiplist.level - 1; i >= 0; i--) {
			while (tmpNode->levels[i].forward && (traversed + tmpNode->levels[i].span) <= rank)
			{
				traversed += tmpNode->levels[i].span;
				tmpNode = tmpNode->levels[i].forward;
			}
			if (traversed == rank) {
				break;
			}
		}
	} while (false);

	if (tmpNode == nullptr)
	{
		return {};
	}
	std::vector<const Value*> resList;
	resList.push_back(&tmpNode->value);
	start++;
	while (start <= end)
	{
		start++;
		tmpNode = tmpNode->levels[0].forward;
		if (tmpNode == nullptr)
		{
			break;
		}
		resList.push_back(&tmpNode->value);
	}
	return std::move(resList);
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL /*= 64*/>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::EachValue(std::function<void(uint32 rank, const Value&)> cb) const
{
	if (m_skiplist.length == 0)
	{
		return ;
	}
	uint32 start = 0;
	const skiplistNode<Key, Value>* tmpNode = m_skiplist.header;
	while (start <= m_skiplist.length)
	{
		tmpNode = tmpNode->levels[0].forward;
		if (tmpNode == nullptr)
		{
			break;
		}
		start++;
		cb(start, tmpNode->value);
	}
}
template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
skiplistNode<Key, Value>* RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::CreateSkipListNode(int level, Value value, Key key)
{
	skiplistNode<Key, Value>* zn = new skiplistNode<Key, Value>(level);
	zn->value = value;
	zn->key = key;
	return zn;
}

template <typename Key, typename Value, int ZSKIPLIST_MAXLEVEL>
void RankSkipList<Key, Value, ZSKIPLIST_MAXLEVEL>::DeleteNodeEx(skiplistNode<Key, Value>* deleteNode, skiplistNode<Key, Value>** update)
{
	int i;
	for (i = 0; i < m_skiplist.level; i++) {
		//如果需要修改的节点的后一个节点是要删除的节点,
		if (update[i]->levels[i].forward == deleteNode) {
			//假设没有删除，此节点到下一节点(deleteNode)的下一个节点的的span = 此节点的span + 删除节点的span,
			//此节点的下一节点删除后，此节点的span等于此节点的span加上删除节点的span - 1
			update[i]->levels[i].span += deleteNode->levels[i].span - 1;
			//赋值后向指针,在每层上看，就是一个链表删除一个节点的操作
			update[i]->levels[i].forward = deleteNode->levels[i].forward;
		}
		else {
			//如果需要修改的节点的后一个节点不是要删除的节点,则说明删除节点的层数小于该层，该层链表之上没有要删除的节点，直接span - 1即可
			update[i]->levels[i].span -= 1;
		}
	}

	//修改地0层的前向指针
	if (deleteNode->levels[0].forward) {
		deleteNode->levels[0].forward->backward = deleteNode->backward;
	}
	else {
		m_skiplist.tail = deleteNode->backward;
	}

	//删除节点后，遍历每层，如果该层之后头头节点，则删除该层
	while (m_skiplist.level > 1 && m_skiplist.header->levels[m_skiplist.level - 1].forward == nullptr)
		m_skiplist.level--;
	m_skiplist.length--;
}
